Detecting a distributed denial-of-service (DDoS) attack on a network, particularly a packet flooding DDoS attack such as a well known TCP-SYN flood attack, is a problem that requires monitoring a very high volume of streaming data having both insertion and deletion events, using a guaranteed small foot print, i.e. a guaranteed small amount of computer memory and processing power.
Any system connected to the Internet and providing Transmission Control Protocol (TCP) based network services (such as a Web server, file transfer protocol (FTP) server, or mail server) is potentially vulnerable to a TCP-SYN flood attack, because of the manner in which a TCP connection is established. When a client device attempts to establish a TCP connection with a server, an initial, pre-determined sequence of messages are exchanged. The client first sends a synch (SYN) message containing its internet protocol (IP) address to the server. The server acknowledges this with a synch acknowledged (SYN-ACK) message and the client responds with an acknowledge (ACK) message to complete the connection.
The potential for abuse arises at the point where the server system has sent a SYN-ACK message back to the client but has not yet received the ACK message, i.e., a half-open connection has been established. The server is vulnerable because the data structure for storing information about each half-open, pending connection has a finite size, and the server has a limited area in which to store these data structures. By creating a large number of half-open connections, the memory allocated for storing this information can be completely filled, at which point the system can no longer process new connections. In some operating systems, when these data structures overflow the memory allocated to them, system data is overwritten and the server crashes.
Creating half-open connections is easily accomplished by IP spoofing, i.e., by making attempts to establish IP connections that look as if they are from a legitimate source, but actually have randomly-chosen, fake IP addresses. As there are no client machines sending these attempts to connect, the connections cannot be completed, resulting in half-open connections that persist until the server removes them. The attacking machine (or machines) attempts to fill, and preferably overflow, the server memory allocated to monitoring pending connections by sending enough spoofed connection attempts. Although there is usually a timeout associated with a half-open connection so that it will eventually expire, the attacking machines may prevail by simply sending IP-spoofed connection requests faster than the victim system expires them.
The impact of successful DDoS attacks can be severe and widespread. The possible damage includes Service-Level-Agreement (SLA) violations, frustrated customers, and cumulative loss of business that can in some cases amount to many millions of dollars.
To prevent such attacks, they have to be detected in real-time so that appropriate action can be taken to mitigate the consequences of the attack, such as diverting all traffic to those sites under attack through specially designed filters such as the SureArmour™ filters supplied by Riverhead Technology of Cupertino, Calif.
The problem of effective and timely detection of such attacks on large internet service providers' (ISP) networks requires algorithms that can operate in real-time in a data-streaming fashion to obtain accurate estimates of destination machines having a large number of distinct half-open connections.
Previous attempts to investigate DDoS attacks have either been done off-line after the attack, or have used hash-based filtering to identify large flows of data to particular sites. An example of a method of detecting large data flow is described by, for instance, Estan et al. in an article entitled “New Directions in Traffic Measurement and Accounting” in the proceedings of the Association for Computing Machinery (ACM) Special Interest Group on Management of Data (SIGMOD) 2002 conference on applications, technologies, architectures, and protocols for computer communications, ISSN:0146-4833, pp 323-336, August 2002, ACM Press, New York, N.Y., the contents of which are hereby incorporated by reference.
Large flows are, however, not necessarily a reliable indicator of DDoS activity as specific types of DDoS, such as the TCP-SYN flooding attack detailed above, do not necessary result in large traffic flows. In a TCP-SYN flooding attack, each malicious, half-open connection requires only a short message, which may be a single packet, to establish. As the SYN-ACK message remains unanswered, with no further traffic flows for that half-open connection, an effective attack can be mounted with data-flows that do not exceed the normal traffic to the site. Furthermore, merely monitoring large flows does not differentiate between DDoS activity and legitimate flash crowds that result in an unexpected surge of legitimate requests following some important event.
The methods proposed by Akella et al. in their article entitled “Detecting DDoS Attacks on ISP Networks” published in the Proceeding of the ACM SIGMOD/PODS Workshop on Management and Processing of Data Streams (MPDS) held in San Diego, Calif., June 2003, published by ACM Press, New York, N.Y., the contents of which are hereby incorporated by reference, have similar limitations as they rely on maintaining profiles of activity only for selected, popular destinations whose traffic exceeds a certain threshold.